//给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 
//
// 回文字符串 是正着读和倒过来读一样的字符串。 
//
// 子字符串 是字符串中的由连续字符组成的一个序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abc"
//输出：3
//解释：三个回文子串: "a", "b", "c"
// 
//
// 示例 2： 
//
// 
//输入：s = "aaa"
//输出：6
//解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 由小写英文字母组成 
// 
//
// Related Topics 双指针 字符串 动态规划 👍 1381 👎 0

package leetcode.editor.cn;
//java:回文子串
public class Q0647PalindromicSubstrings {
    public static void main(String[] args){
        Solution solution = new Q0647PalindromicSubstrings().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /**
         * 方法一：双指针
         */
    public int countSubstrings(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            // 分别计算以i为中心或者以i + 1为中心向外扩散的个数
            res += countSubStr(s, i , i, s.length());
            res += countSubStr(s, i , i + 1, s.length());
        }
        return res;
    }

    public int countSubStr(String s, int left, int right, int len) {
        int res = 0;
        while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
            res++;
        }
        return res;
    }

        /**
         * 方法二：动态规划
         */
//        public int countSubstrings(String s) {
//            if (s == null || s.length() == 0) return 0;
//            int n = s.length(), res = 0;
//            //1.dp[i][j] 表示[i,j]之间的是否是回文串
//            boolean[][] dp = new boolean[n][n];
//            // 3. 初始化,全是false
//            // 4. 遍历顺序有些不同
//            for (int i = n - 1; i >= 0; i--) {
//                for (int j = i; j < n; j++) {
//                    // 2.递推公式
//                    if (s.charAt(i) == s.charAt(j)) {
//                        // 同一个字符，或者前后两个一样的字符
//                        if (j - i <= 1) {
//                            res++;
//                            dp[i][j] = true;
//                        // 看看子字符是不是回文
//                        // 按道理说dp[i+1]可能越界，需要在初始化中排除，但是这里在条件后，i不会越界
//                        } else if (dp[i + 1][j - 1]) {
//                            res++;
//                            dp[i][j] = true;
//                        }
//                    }
//                    // 不相等默认false
//                }
//            }
//            return res;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}